\section{Descripción del Problema}

Una empresa que transporta productos químicos necesita transportar $n$ productos en distintos camiones. Los productos a transportar presentan un nivel de peligrosidad de a pares(que se conoce de ante mano). 
 No existe un límite de camiones, sin embargo se nos pide dar a conocer la mínima cantidad de camiones posibles tal que se cumplan las normas vigentes de seguridad.
 En cada camión, la suma de peligrosidades(de a pares) de todos los elementos que lleva, no puede exeder un cierto umbral $M$.
 Se nos pide diseñar un algoritmo de \textit{Backtracking} para resolver este problema.\\
Los parámetros son los siguientes:
\begin{itemize}
\item Dos enteros \textbf{n} y \textbf{M} $\rightarrow$ Representarán el número de productos y umbral de peligrosidad permitido para cada camión.
\item $n-1$ líneas que indican los coeficientes de peligrosidad de cada par de productos. En la línea $i$ encontramos el nivel de peligrosidad del $producto i$ con los demás productos
\end{itemize}

\subsection{Ejemplo}
Una posible instancia del problema, podr\'ia ser: 
\textbf{n} $= 5$, \textbf{m} $= 10$
Luego cada línea $i$ representa las peligrodidades del producto $i$ con los productos $i+1$ en adelante
\begin{itemize}
\item[\textbf{Prod 1:}] $1_{pel}2 = 5$, $1_{pel}3 = 1$, $1_{pel}4 = 7$, $1_{pel}5 = 9$
\item[\textbf{Prod 2:}] $2_{pel}3 = 3$, $2_{pel}4 = 7$, $2_{pel}5 = 6$
\item[\textbf{Prod 3:}] $3_{pel}4 = 1$, $3_{pel}5 = 8$
\item[\textbf{Prod 4:}] $4_{pel}5 = 3$
\end{itemize}

En este caso una posible soluci\'on ser\'ia la siguiente: $~~~$
2 camiones
\begin{itemize}
\item camión 1: Prod4 y Prod5, total nivel de pelig: 3 
\item camión 2: Prod1, Prod2 y Prod3, total nivel de pelig: 9 
\end{itemize}

Este es un caso sencillo, pero a\'un as\'i ya tenemos muchísimas permutaciones distintas para probarlas como soluci\'on.
A simple vista se ve que mientras mas grande la cantidad de productos el nivel de complejidad aumenta dr\'asticamente.


\section{Idea General de la Resolución}

Supongamos que dado el problema contamos con una solucion parcial
en la que hay un conjunto de cargas ubicadas ya en un par de camiones y 
otro conjunto de cargas aun no ubicadas. En este momento 
la desición  que tome al ubicar alguna de las cargas disponibles 
en uno de los dos camiones alterara  la cantidad 
de camiones de la solucion final. No hay forma 
de saber a priori  en que camion debo ubicar una  carga. 
La unica alternativa que tengo es probar
todas las combinaciones.Teniendo una solucion parcial con $k$ cargas disponibles debo probar para cada
una, agregarla a cada uno de los camiones y
llamar recursivamente a mi algoritmo para resolver ese subproblema de $k-1$ cargas con 
la solucion parcial que tengo.
Tambien debo probar agregar un camion adicional para esa carga, esto 
es otra alternativa que tambien tengo que evaluar.  \\
Probar  todas las cargas con  todos los camiones y sabiendo que mi algoritmo 
para una subsolucion con $k-1$ 
cargas, evaluara todas las posibilidades y devolvera la optima,
entonces la mecanica sera tomar una desición  y llamar recursivamente 
al algoritmo para ver en el resultado si esa desición  es la que 
hace que a futuro en el subproblema se mejore el resultado global.\\
La llamada recursiva en la que se plantea la resolucion 
de un subproblema en base a una solucion parcial se hace luego de
haber de alguna manera afectado una solucion parcial recibida como parametro. Por
lo tanto lo que hago en cada llamada del algoritmo es probar todas 
las variables posibles que puedo tocar para afectar el resultado final y 
llamar con esos cambios en la solucion parcial recursivamente. 
A la vuelta de la llamada veo como afecta esa desición  en el resultado 
final. Esto me asegura no hacer ningun tipo de suposicion
a priori en base a informacion local. Cada cambio que hago 
lo evaluo en funcion de su resultado sobre la solucion final. \\

\subsection{Podas}
En el esquema planteado en el que produzco modificaciones sobre una solucion parcial, llamo
recursivamente y evaluo si ese cambio es el que produce un mejor resultado final  a 
futuro. Se implemento una poda para que dentro de todas las combinaciones posibles que se evaluan,
descartar aquellas que se que no me agregan nada nuevo en la busqueda del resultado optimo. 
Dada una solucion parcial que recibo como parametro y un valor de referencia sobre cual
es la mejor solucion que conozco hasta el momento. El algoritmo no retornara una solucion 
que no sea mejor a ese parametro. Esto sirve para que el algoritmo no devuelva hacia el 
llamado que esta por sobre este en el arbol de llamadas, un resultado que no sea mejor 
que este parametro. De esta manera cualquier  instancia del arbol de llamadas
que se produce con la recurcion, no retornara un resultado que no mejore
la mejor solucion conocida. \\ Esto el efecto que tiene es que 
si la mejor solucion conocida tiene $k$ camiones, no voy a intentar agregar 
un camion a la solucion parcial que estoy evaluando, si esta ya posee $k-1$ camiones. 
Eso haria que la solucion parcial, en el mejor de los casos tenga igualmente $k$ camiones 
con lo que por esa rama de soluciones nunca voy a poder mejorar los resultados anteriores.\\
Esto hara que el algoritmo corte esta rama de soluciones.  



\subsection{Pseudoc\'odigo}

\begin{verbatim} 
     

    // CargasDisponibles: es un arreglo/lista de las cargas que aun deben ubicarse 
    // LimiteCamiones: mejor solucion que pude conseguir hasta ahora(poda). 
                      // en el primer llamado este numero es fijado 
                      //en el valor entero maximo.                      
    // LimitePeligro: limite de peligro que puede soportar un camion
    // Solucion: solucion parcial del problema, con algunas cargas ya ubicadas 
                // y el resto esta en CargasDisponibles
                // la primer llamada se hace con una solucion en la 
                //que no hay camiones aun. 

O( F(n)) Resultado UbicarCargas(CargasDisponibles,LimiteCamiones,LimitePeligro,Solucion)
        - MejorSolucion = Nulo.
        - MejorCantidad = +Infinito. 

O(n)        - Para cada carga 'C' dentro de las cargas disponibles
            - retiro  la carga 'C' de las disponibles.
O(i)            - Para cada camion 'ca' dentro de Solucion, mi solucion parcial. 
O(i)                - ubicar 'C' en ese camion siempre y cuando no supere 
                       el limite de peligro. 
O( F(n-1))          - llamar recursivamente con CargasDisponibles \ 'C' para 
                       mi nueva subsolucion con 'C' en 'ca'
                - si el resultado de la llamada recursiva necesita menos camiones 
                   que MejorSolucion actualizo MejorSolucion y LimiteCamiones.
                   // Si MejorSolucion es nulo cualquier solucion es mejor
                   //ahora la mejor solucion que conozco tiene 'LimiteCamiones'

            - si la cantidad de cargas de 'Solucion' es menor que LimiteCamiones -1
              // todabia puedo agregar un camion y ser mejor solucion 
              // que la mejor conocida 
              - agrego un camion y ubico 'C' en este nuevo camion. 
O( F(n-1))              - llamo recursivamente con la nueva subsolucion que 
                  agrega un camion con 'C' a la solucion recibida. 
              - si el resultado de la llamada recursiva es mejor 
                 que MejorSolucion, actualizo MejorSolucion y LimiteCamiones.
                // Si MejorSolucion es nulo cualquier solucion es mejor
                //ahora la mejor solucion que conozco tiene 'LimiteCamiones'
            
        Retornar MejorSolucion    
\end{verbatim}

\section{Complejidad}

% Para demostrar la correctitud lo hacemos 
% por induccion fuerte.
% Para 2 items es facil ver y es nuestro caso base. \\
% Dados 2 items podemos ver que si la suma de los items es mayor que el peligro maximo
% permitido entonces ambas no seran ubicadas en el mismo camion y 
% que al buscar un camion para la segunda carga debera agregarse el segundo camion. 
% En caso que la suma sea menor que el peligro maximo entonces ambas cargas viajaran juntas.
% Esto demuestra que el algoritmo en el caso de 2 cargas da un resultado optimo.\\
% Si para cualquiera de las k-1 cargas que tome siempre voy obtener
% la solucion optima luego viendo de esas k-1 subsoluciones cual me hace
% utilizar la menor cantidad de camiones al agregar la carga k voy  a 
% estar seguro que la solucion es la optima para las K cargas.\\
% Para estar seguros veamos que pasa si suponemos que no\\
% \\
% Supongamos que no, que hay una permutacion de k-1 cargas que hace que
% al agregar la carga K se tenga una solucion con menor cantidad de camiones. 
% Este caso seria uno en el que dadas las mismas K-1 cargas {k1,,,,k-1}
% ambas soluciones dan como resultado C camiones pero al querer agregar
% la carga K a ambos resultados uno requiere que se agrege un camion y el otro no.

% Esto quiere decir que en la solucion que no se agrega un camion existe
% un camion donde entra la carga K sin sobrepasar el peligro maximo. \\




% \subsection{Cota de Complejidad}
La implementacion es recursiva y descompone un 
problema de $n$ cargas en $(n-i) * (i+1)$  subproblemas de $n-i-1$ cargas. 
Donde $i$ corresponde al nivel de recursion o profundidad, que a su vez
coincide con la cantidad de cargas ubicadas, y $n$ coincide
con la cantidad de cargas totales. El nivel de recursion
$i$ tiene rango $0\leq i \leq n-1$

Como se puede ver en el pseudocodigo hay un for loop doble ,
uno sobre las cargas disponibles y otro sobre la cantidad de camiones.
Esto hace que al tener $i$ cargas ya ubicadas en la solucion 
parcial, pueda iterar unicamente sobre $n-i$ cargas disponibles y
sobre a lo sumo $i$ camiones. 

    
% Para la llamada $i$(profundidad en la recursion) de cada uno de los subproblemas se debe copiar la lista 
% de cargas disponibles(seran $n-i$ si estoy a una profundidad $i$ en el arbol de recursion
% ), asi como el resultado parcial hasta ese momento. 



En el body de estos 2 loops se toma una carga de las disponibles
y se agrega a la solucion parcial para con estos cambios
llamar recursivamente. 
Estas operaciones de construccion de una nueva
solucion se hacen en tiempo lineal en funcion de la cantidad de
cargas.\\

La copia de las cargas disponibles es un vector de $n-i$ valores/cargas.
El resultado parcial consta de un valor escalar, la lista de camiones con sus cargas $i$  
cargas entre todos los  camiones
y la lista de los valores que suman en peligrosidad cada uno de los camiones siendo $i$ a lo sumo. 
Estos dos objetos pueden copiarse en tiempo lineal,
 $(n-i) + (i) +  (i)$ operaciones. \\


%Si estamos a profundidad $i$ en la recursion
%tendremos a lo sumo $i$ camiones y por lo tanto las unicas operaciones
%no constantes son la de sumar las cargas de los camiones al agregar una nueva a un camion.\\
%Esto como se apunto en el pseudocodigo se hace en tiempo a lo sumo $i$

\\
Para cada una de las $(n-i)*(i+1)$ iteraciones tengo un costo $i$ en la suma de peligros
mas la copia del resultado parcial, luego  
se hara una llamada recursiva a un problema similar con $n-i-1$ cargas.\\

Si calculamos la cantidad de subproblemas y la complejidad del for loop  doble
por otro lado tenemos :\\

$\prod_{i=0}^{n-1}_{( n-i) * (i+1) } $ 
problemas independientes con complejidad $ ((2i)+(n-i)) $ dependiendo \\del 
nivel de profundidad en la recursion. 

$ ((2i)+(n-i)) \prod_{i=0}^{n-1}_{( n-i) * (i+1) }  \leq (2n)* \prod_{i=0}^{n-1}_{n/2 * n/2}  \leq $\\

$(2n)* \prod_{i=0}^{n-1}_{n^2/4 } \leq (2n)* (n^2/4)^n  } $ \\
\\
Estos calculos nos llevan a afirmar que la cota del algoritmo sera  $O( (2n) * (n^2/4)^n  ) $.
 

\section{Testing}
Para la experimentacion se utilizaron entradas generadas al azar. En
ellas se tuvo en cuenta que determinadas combinaciones de valores
hacian que la complejidad y el resultado observado tuviera poca utilidad como
por ejemplo el caso en el que el limite de peligrosidad de los
camiones hacia que ninguna carga pudiera viajar acompañada. En 
este caso el problema se reduce a ubicar una carga por camion. 
Esto elimina la complejidad de tener que ver como armar los conjuntos
de cargas por que cualquier permutacion que genere excede 
el limite soportado por el camion.\\
En cuanto a la cantidad de cargas que es el factor que influye 
directamente en la complejidad del problema, dado que aumenta la cantidad
de permutaciones para los conjuntos de cargas que van en los camiones, se pudo llegar
hasta un maximo de 10 cargas con  poda y 8 sin . Por sobre las 10 cargas no se logro tener solucion 
en un tiempo razonable.  Para este rango entonces, con cargas desde 5 hasta 10
y variando los valores de peligrosidad de a pares entre 1 y 6, se pudo
ver como aumentaba la complejidad y con que forma.\\
El grafico fue suavisado aplicando la funcion logaritmo sobre los tiempos
tomados. De esta manera puede mantenerse una escala que permita ver 
mas  claramente la velocidad con la que aumenta la complejidad. 
Se realizaron mediciones con la poda, sin esta y esa informacion
se la cruzo con la funcion  $(n^2/4)^n$ tambien suavisada con el logaritmo.
Estas 3 lineas como varia la complejidad en el caso de no utilizar poda y 
tambien la proximidad de la cota de complejidad con los valores observados.\\
En un primer momento se hizo una estimacion de complejidad que luego 
al realizar las pruebas no se aproximaba bien a los valores observados. 
En ese momento y luego de investigar y revisar varias veces el calculo de 
complejidad se corrigio. Tambien surgio en ese momento el tema de que las podas 
no eran tenidas en cuenta y eso reducia la complejidad. En ese momento se 
decidio graficar esta diferencia. Desde el punto de vista 
de la implementacion no se  implementar tecnicas de poda que se 
consideraran mejores que la que se utilizo. Se utilizo solo una y 
cualquier otra poda se descarto o por tiempos de desarrollo o 
por no considerarse lo suficientemente eficiente en la reduccion de costos. \\
Las diferencias que se pueden ver entre la curva de complejidad 
y la observada tambien se penso en evaluarla sin considerar los costos de copia 
de objetos en el algoritmo. Se obviaron estos costos y en el nuevo valor de  complejidad
resultante se grafico. Esto no ajustaba tampoco exactamente a la complejidad observada. 
Tambien una de las cosas que complejiza el analisis es la poca cantidad de cargas que se 
podian evaluar dado que con estos pocos puntos es dificil deducir como ajusta la linea 
de complejidad teorica a los observado. 



\includegraphics[scale=0.7]{imagenes/Biohazard1.png} 
\\

\section{Adicionales}

\subsection{Como afecta a su algoritmo}

Para poder tener camiones con distintos limites de peligrosidad lo unico que debe tenerse 
en cuenta  al momento de agregar una carga a un camion es evaluar 
cual es el limite de ese camion en particular. 
Habra que tener un vector con los limites para cada uno de los camiones actuales. \\
En la implementacion original la funcion pasa como parametro un valor entero que es el limite
de peligro de los camiones. Ahora con este cambio ese entero 
pasara a ser un vector que se pasa como parametro y que para cada uno de los camiones
indica cual es el limite de peligro. Solo debera agregarse la logica para copiar este vector.
\subsection{Que cosas se podian hacer antes y ahora no se puden en base a estos cambios}
Las podas que se implementaron utilizan la mejor cantidad de camiones 
encontrada hasta el momento como forma de cortar 
el arbol de soluciones y sacar aquellas que no mejoran estos valores. 
Se esta suponiendo para esta poda que todos los camiones poseen el mismo 
limite o por lo menos que cada vez que se agrega un camion los limites 
de peligro de estos conservan un orden. Por lo que si tomo 3 camiones siempre
los limites de peligro seran los mismo y en el mismo orden. Si tomo cuatro lo mismo y asi.
De esta menera comparo soluciones siempre sobre el mismo conjunto de camiones.
\\
\\
Hay un poda que se puede implementar y no se hizo en la primera version que es, 
tener una tabla con secuencias de  cargas que ya se sabe que no pueden estar
juntas dado que superan el limite de peligrosidad. 
Esto hara que cualquier intento de agregar una carga  a un 
camion sea buscado primero en esta tabla. 
De esta 
manera si en un paso, se intenta por ej junta las cargas $1,2,3$
y eso supera el limite de peligro de todos los camiones, se puede 
guardar esta combinacion como una que no puede darse. El problema
con la implementacion de esta poda es que generar la clave para el diccionario
de combinaciones de carga tiene un costo y la mejora o la baja
que se produce es solo para la funcion que suma el peligro de un camion. 
Con lo cual esta poda no parece ser buena. Por ahi se podria 
limitar esto a combinaciones de no mas de 3 cargas, osea que si hay 3 cargar que 
superan el maximo de peligro, lo registro para su posterior uso. 
\\
Esta poda y cualquier que se plantee utilizando informacion de cargas y el limite de peligrosidad
en base a un intento hecho en un camion que se quiera reutilizar para otro camion 
resultara invalida a no ser que tengan el mismo limite de peligro.

\section{Codigo Fuente}


\verbatiminput{../src/ej3/ej3.cpp}
 